package leetcode.top100;

import java.util.*;

/**
 * @since 2019/12/23 0023 上午 11:18
 */
public class Code621_TaskScheduling_任务调度器 {
    public static void main(String[] args) {
        char[] tasks = {'A', 'A', 'A', 'B'};
        System.out.println(leastInterval(tasks, 2));
    }

    public static int leastInterval(char[] tasks, int n) {
        if (tasks == null || tasks.length == 0) return 0;
        return process2(tasks, n);
    }

    /**
     * 方式3：策略调度。时间复杂度O(M),M是任务总数。空间O(1)
     */
    private static int process3(char[] tasks, int n) {
        //设定一个A-Z的数组，把任务个数统计
        int[] map = new int[26];
        for (char task : tasks) {
            map[task - 'A']++;
        }
        Arrays.sort(map);
        int retCount = (map[25] - 1) * (n + 1) + 1;
        int i = 24;
        // 统计和最多任务数一样多的个数。让retCount ++
        while (i >= 0 && map[i] == map[25]) {
            retCount++;
            i--;
        }
        return Math.max(retCount, tasks.length);
    }

    /**
     * 方式2：使用优先级队列 ，思路同方式1，贪心
     * <p>
     * 时间O(time),空间O(1)，只是开辟常数个空间26
     */
    private static int process2(char[] tasks, int n) {
        //设定一个A-Z的数组，把任务个数统计
        int[] map = new int[26];
        for (char task : tasks) {
            map[task - 'A']++;
        }
        int time = 0;
        //大根堆
        Queue<Integer> queue
                = new PriorityQueue<>(26, (o1, o2) -> o2 - o1);
        //把次数放入大根堆
        for (int e : map) {
            if (e > 0) queue.add(e);
        }
        while (!queue.isEmpty()) {
            int i = 0;
            List<Integer> temp = new LinkedList<>();
            while (i <= n) {
                if (queue.isEmpty() && temp.isEmpty()) break;
                //如果任务不空
                if (!queue.isEmpty()) {
                    //如果当前任务次数大于1，那么减掉1次
                    if (queue.peek() > 1) {
                        //poll是把当前任务给排干
                        temp.add(queue.poll() - 1);
                    } else {
                        //任务等于1，不用存
                        queue.poll();
                    }
                }
                i++;
                time++;
            }
            //重新把剩余任务放入堆
            queue.addAll(temp);
        }
        return time;
    }

    /**
     * 方式1：基于排序的调度算法，贪心
     * <p>
     * 时间复杂度：O(time)，给每个任务都安排了时间，因此时间复杂度和最终的答案成正比。
     * <p>
     * 空间复杂度：O(1)。
     */
    private static int process1(char[] tasks, int n) {
        //设定一个A-Z的数组，把任务个数统计
        int[] map = new int[26];
        for (char task : tasks) {
            map[task - 'A']++;
        }
        //对任务进行排序,先执行任务多的
        Arrays.sort(map);
        int time = 0;
        //如果最多的任务还没完成
        while (map[25] > 0) {
            //i表示当前轮次执行的次数，在冷却时间n内不能连续执行同一个任务
            int i = 0;
            //冷却时间是n,代表同一个任务执行完毕后要等待n次才能再执行该任务。所以总共一轮是n+1次。 所以是i<=n
            while (i <= n) {
                //如果最多的任务都执行完了，代表所有任务都执行完了
                if (map[25] == 0) break;
                //如果要执行的任务还有次数，则执行
                if (i < 26 && map[25 - i] != 0) map[25 - i]--;
                //当前轮次执行的次数
                i++;
                //执行总次数
                time++;
            }
            //对任务进行新一轮的排序
            Arrays.sort(map);
        }
        return time;
    }
}
